Asal-usul nama ‘Sabah’ dipercayai berasal daripada sejenis tanaman iaitu pisang yang dikenali sebagai pisang Saba iaitu sejenis buah pisang yang dipanggil " SAING SABBAH " atau "SAPPAH" oleh masyarakat tempatan yang sangat popular. Pisang ini banyak ditanam di sepanjang pantai barat Sabah sebagai sumber makanan. 'Pisang saba' juga dikenali sebagai 'jaba' oleh masyarakat Bajau di negara tersebut. Kini 'pisang saba' lebih dikenali sebagai pisang menurun.

Nama 'Sabah' pertama kali digunakan pada abad ke-15 oleh para pedagang yang mengembara di antara Kepulauan Borneo Utara hingga ke kepulauan Sulu di Selatan Filipina. Kesimpulannya nama 'Sabah' telah pun digunakan sejak sebelum kedatangan Syarikat Berpiagam Borneo Utara dan British lagi. Dalam peta Portugis Melaka 1604, Kota Kinabalu disebut sebagai Api-Api.

Setelah negara Sabah diambil alih oleh Syarikat Berpiagam Borneo Utara, nama 'Sabah' telah ditukar kepada 'Borneo Utara' secara rasmi pada tahun 1881. Walau bagaimanapun, nama 'Sabah' kembali digunakan pada tahun 1963 ketika pembentukan Malaysia.

Catatan puisi Jawa Nagarakertagama yang dikarang oleh Prapancha pada tahun 1365 menyebut Sabah sebagai 'Seludang'. Dalam catatan Marco Polo sewaktu beliau singgah di Borneo, Sabah ketika itu dikenali sebagai "BURNI" yang mungkin merujuk kepada Brunei.